
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1148. -- [CTSC2007]挂缀pendant
</title><center><h2>1148: [CTSC2007]挂缀pendant
</h2><span class=green>Time Limit: </span>40 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>118&nbsp;&nbsp;<span class=green>Solved: </span>48<br>[<a href='submitpage.php?id=1148'>Submit</a>][<a href='problemstatus.php?id=1148'>Status</a>][<a href='bbs.php?id=1148'>Discuss</a>]</center><h2>Description</h2><div class=content>“珠缀花蕊，人间几多酸泪”……
挂缀在很早就被人们作为一种装饰品，垂坠的风韵，华丽摇曳的摆动，展现出一种与众不同的优雅与高贵。而我们的主人公小Q，正想买一条漂亮的挂缀放在寝室里作为装饰。
挂坠的构成，是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成：分别是珠子、珠子上方的连接环与珠子下方的挂钩（如下图）。我们可以简单的认为从上往下数的第i个缀珠是将它的连接环套在其上方（也就是第i-1个）缀珠的挂钩之上（第一个除外）。小Q想买一根足够长的挂缀，这样显得更有韵味&#61514;
 
然而商店的老板告诉小Q，挂缀是不可能做到任意长的，因为每一个珠子都受到重力作用，对其上方的挂钩有一定的拉力，而挂钩的承受能力是有限的。老板还告诉小Q，他一共拥有N个珠缀（假设每一个珠缀都很漂亮，小Q都很喜欢），每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的，当且仅当对于其上的每一个珠缀，它下方所有珠缀的重量和（不包含自身）不超过其挂钩的承受能力。
小Q希望她的挂缀尽量长，你能帮她计算出最长可能的稳定挂缀么？当然，如果有多个可选方案，小Q希望总重量最小的。
</div><h2>Input</h2><div class=content>第一行包含一个正整数N，表示商店拥有的珠缀数目。接下来N行，每行两个整数(Ci , Wi)，分别表示第i个珠缀的承受能力与重量。
</div><h2>Output</h2><div class=content>包行两行。第一行包含一个整数L，表示可以找到的最长稳定挂缀长度。第二行包含一个整数W，表示可以找到的长度为L的稳定挂缀中的最小重量和。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4<br />
3 5<br />
5 1<br />
3 2<br />
4 6<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3<br />
8<br />
</span></div><h2>HINT</h2>
			<div class=content><p>每一个测试点单独评分，对于每一个测试点：<br />
如果挂缀长度L与答案一致，且最小重量和W也正确，则得10分。<br />
如果挂缀长度L与答案一致，而最小重量和W与答案不一致，该测试点则得4分。<br />
否则得0分。<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1148'>Submit</a>][<a href='problemstatus.php?id=1148'>Status</a>][<a href='bbs.php?id=1148'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
